# coding=utf-8
import itertools


def prase(lst):
    return ''.join([str(i) if i < 0
                           else lst.index(i) != 0 and '+' + str(i) or str(i)
                           for i in lst])

def guess(number_base, answer):
    '''从number_base中任选n个,利用加减法凑出答案answer,n个数字不能重复使用
       例如:
            number_base = [1, 2, 3, 4, 5]
            answer = 8
            可能的正确结果如下;
                1 + 2 + 5
                1 - 2 + 4 + 5
                ...
    '''
    tag_base = range(len(number_base))
    count = 0
    result = []
    for i in range(len(number_base)):
        lsts = list(itertools.combinations(number_base, i))
        tags = list(itertools.combinations(tag_base, i))
        for l in lsts:
            for t in tags:
                count += 1
                sub_lst = [i if l.index(i) not in t else -1*i for i in l]
                if sum(sub_lst) == answer:
                    result.append(sub_lst)

    lst = [prase(r) for r in result]
    # import sets
    # result = sets.Set(lst)
    # tips:
    # Deprecated since version 2.6:
    # The built-in set/frozenset types replace this module.
    # see: https://docs.python.org/2/library/sets.html?highlight=sets#module-sets

    result = set(lst)
    print list(result), count

if __name__ == '__main__':
    number_base = [47, 155, 199, 204, 183, 69, 297, 343]
    answer = 400
    guess(number_base, answer)

# output:
# ['-47+155+199-204+297', '155+199-297+343']
